package com.lsa.edmonds.chap5;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NavigableMap;
import java.util.TreeMap;
import java.util.Map.Entry;

import com.lsa.helpers.IntArrayListAdapter;
import com.lsa.helpers.Utils;
import com.lsa.shenn.common.Sorter;

public class CountingSort implements Sorter
{
	@Override
	public int[] sort(int[] array)
	{
		List<Integer> list = new IntArrayListAdapter(array);
		list = sort(list);
		return Utils.toPrimitiveArray(list);
	}

	@Override
	public List<Integer> sort(List<Integer> array)
	{
		NavigableMap<Integer, Integer> int2Count = new TreeMap<Integer, Integer>();
		
		for (int i = 0; i < array.size(); i++)
		{
			int count = 0;
			
			Integer nCount = int2Count.get(Integer.valueOf(array.get(i)));
			if (nCount != null)
			{
				count = nCount.intValue();
			}
			
			int2Count.put(array.get(i), ++count);
		}
		
		NavigableMap<Integer, Integer> int2CountLessThen = new TreeMap<Integer, Integer>();
		if (!int2Count.isEmpty())
		{
			Integer nLowest = int2Count.firstKey();
			int2CountLessThen.put(nLowest, 0);
		}
		
		for (Iterator<Entry<Integer, Integer>> iterator = int2Count.entrySet().iterator(); iterator.hasNext();)
		{
			Entry<Integer, Integer> nInt2CountEntry =  iterator.next();
			
			Entry<Integer, Integer> entryCountLessThenPrev = int2CountLessThen.floorEntry(nInt2CountEntry.getKey() - 1);
			Integer nCountLessThenPrev = Integer.valueOf(0);
			if (entryCountLessThenPrev != null )
			{
				nCountLessThenPrev = entryCountLessThenPrev.getValue();
			}
			
			Integer nCountPrev = Integer.valueOf(0);
			Entry<Integer, Integer> entrynCountPrev = int2Count.floorEntry(nInt2CountEntry.getKey() - 1);
			if (entrynCountPrev != null )
			{
				nCountPrev = entrynCountPrev.getValue();
			}
			
			int2CountLessThen.put(nInt2CountEntry.getKey(), nCountLessThenPrev + nCountPrev );
		}
		
		List<Integer> returnArray = new ArrayList<Integer>();
		returnArray.addAll(array);
		
		for (int i = 0; i < array.size(); i++)
		{
			int idx = int2CountLessThen.get(array.get(i));
			returnArray.set(idx++, array.get(i));
			int2CountLessThen.put(array.get(i), idx);
		}
		
		return returnArray;
	}

}
